package main

type ListNode struct {
	Val  int
	Next *ListNode
}

func partition(head *ListNode, x int) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	hair := &ListNode{Next: head}
	less := &ListNode{}
	n := hair
	m := less
	for n.Next != nil {
		if n.Next.Val < x {
			// 从初始位置移除 n.Next
			n1 := n.Next
			n.Next = n1.Next
			// 插入到 insert 后
			m.Next = n1
			m = m.Next
			continue
		}
		n = n.Next
	}
	m.Next = hair.Next
	return less.Next
}

func main() {
	head := &ListNode{
		Val: 1,
		Next: &ListNode{
			Val: 4,
			Next: &ListNode{
				Val: 3,
				Next: &ListNode{
					Val: 2,
					Next: &ListNode{
						Val: 5,
						Next: &ListNode{
							Val: 2,
						},
					},
				},
			},
		},
	}
	result := partition(head, 3)
	println(result)
}
